package 开始的剑指offer8月.链表;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

// https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
public class 剑指Offer06从尾到头打印链表0814 {
// 按下 alt+capslk  ，用鼠标左键拖动。
    class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }
      //递归方法
    class Solution {
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        public int[] reversePrint(ListNode head) {
            recur(head);
            int[] res = new int[tmp.size()];
            for(int i = 0; i < res.length; i++)
                res[i] = tmp.get(i);
            return res;
        }
        void recur(ListNode head) {
            if(head == null) return;
            recur(head.next);
            tmp.add(head.val);
        }
    }

    //栈
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
    //辅助栈
    // https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/mian-shi-ti-06-cong-wei-dao-tou-da-yin-lian-biao-d/
    class Solution2 {
        public int[] reversePrint(ListNode head) {
            LinkedList<Integer> stack = new LinkedList<Integer>();
            while(head != null) {
                stack.addLast(head.val);
                head = head.next;
            }
            int[] res = new int[stack.size()];
            for(int i = 0; i < res.length; i++)
                res[i] = stack.removeLast();
            return res;
        }
    }


}
